1. Field of the Invention
The present invention relates to data processing, and more particularly to apparatus and method for managing a file allocation table more efficiently.
2. Description of Related Art
The FAT file system is well known and is described in several publications including IBM DISK OPERATING SYSTEM TECHNICAL REFERENCE, July 1988, published by IBM, which is hereby incorporated by reference. Briefly, in a FAT file system, a disk is divided into clusters of 512 byte sectors. A file is stored in one or more clusters dependent upon the file length. The disk also contains a boot record, a file allocation table (FAT), a root directory, and a data area containing subdirectories and files. The directory is a tree structured directory system. A given file is found by specifying the drive it is on, the directory path, and a filename, e.g., c:/dir1/dir2/filename.ext.
FIG. 1 shows a block diagram of the disk format of the FAT file system. A brief description of the FAT file system follows. The FAT file system revolves around the File Allocation Table (FAT). Each logical volume is associated with its own FAT, which serves two important functions: it contains the allocation information for each file on the volume in the form of linked lists of allocation units and it indicates which allocation clusters are free for assignment to a file that is being created or extended. When a disk is formatted in accordance with the FAT file system, a boot sector is written in sector zero. This is followed by one or more file allocation tables. Each file allocation table is physically located on one or more definable FAT storage units of the formatted disk. Although the definable FAT storage unit is typically a 512 byte sector on the external disk storage device, it is understood that the size of the FAT storage unit may be greater or less than 512 bytes, such as 256 bytes or 1024 bytes. The file allocation tables are followed by a root directory. The root directory is followed by the volume files. The boot sector contains various descriptive information such as the volume in an area referred to as the boot parameter block or BPB, a drive number and a volume I.D., the number of sectors per FAT, as well as a bootstrap routine.
The file allocation table is divided into fields that correspond directly to the assignable clusters on a disk. The first two FAT entries are reserved and the remaining FAT entries describe the use of the corresponding disk clusters. Each file's entry in a root directory contains the number of the first cluster assigned to that file, which is used as an entry point into the FAT. From the entry point on, each FAT field contains the number of the next cluster in the file, until an end-of-cluster mark is encountered. FIG. 2 illustrates an example of a portion of a file allocation table, which specifically indicates the linked list of the clusters allocated to a file.
The FAT system is not only used in personal computer, notebook computer and but also used in some relatively small consumer electronic products, such as digital music players and cameras, personal digital assistants (PDAs), video cameras, cellular phones, and so on. Generally, when accessing the files stored in a hard disk, a memory card or an external storage device, the FAT has to be first read into a ROM of a computer or buffer storage of a consumer electronic product. With the information of the FAT, a central processing unit (CPU) can send the appropriate access commands to the storage to access a desired file stored on the external storage device.
The FAT might be small enough to be retained in the random access memory (ROM) of the commonly used personal computer (PC) or notebook computer at all times. However, the FAT can become relatively too large to be held in the buffer storage of some relatively small consumer electronic products at all times (e.g., a PDA), thus degrading the system performance and data throughput of a device. In any case, the center processing unit in a device, regardless it is a PC, a notebook and a consumer electronic product, manages directly the FAT, thereby occupying some resource of the CPU and adversely effecting performance of other tasks that need the resource of the CPU to perform.
Thus there is a need for techniques for accessing a file allocation table more efficiently with minimum impact on the resource of a CPU.